package main.Q2501_2600;

import java.util.Arrays;

public class Q2511_2520 {
    public static void main(String[] args) {
        System.out.println("Question2511：");
        System.out.println("Question2512：");
        System.out.println("Question2513：");
        System.out.println("Question2514：");
        System.out.println("Question2515：");
        System.out.println("Question2516：");
        System.out.println("Question2517：礼盒的最大甜蜜度");
        int[] price=new int[]{13,5,1,8,21,2};
        System.out.println(new Question2517().maximumTastiness(price,3));
        System.out.println("Question2518：");
        System.out.println("Question2519：");
        System.out.println("Question2520：");
    }
}

class Question2517 {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int left = 0, right = price[price.length - 1] - price[0];
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (process(price, k, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    public boolean process(int[] price, int k, int tastiness) {
        int prev = Integer.MIN_VALUE / 2;
        int cnt = 0;
        for (int p : price) {
            if (p - prev >= tastiness) {
                cnt++;
                prev = p;
            }
        }
        return cnt >= k;
    }
}